/**
 * 
 */
package array.passed;

import java.util.LinkedList;
import java.util.List;

import utils.HelpUtils;

/**
 * @author Michael
 * 
 * in an array of size n, there are n-k unique numbers,
 * all the numbers are in the range [0,n-1], find the k
 * missing numbers.
 */
public class FindKMissingNumber {

	/*
	 * { 1, 2, 1, 2, 3 }
	 * i: 0
	 * index: 1
	 * arr[index] = 2
	 * { 1, -3, 1, 2, 3 }
	 * i: 1
	 * index: -3, 2
	 * arr[index] = 1
	 * { 1, -3, -4, 2, 3 }
	 * i: 2
	 * index: -4, 1
	 * { 1, -3, -4, 2, 3 }
	 * i: 3
	 * index: 2
	 * arr[index] = -4
	 * { 1, -3, -4, 2, 3 }
	 * i: 4
	 * index: 3
	 * arr[index]: 2
	 * { 1, -3, -4, -3, 3 }
	 * 
	 * { 1, 2, 1, 2, 3 }
	 */
	public static void findMissingNumbers(int[] arr) {
		int count = arr.length;
		for (int i = 0; i < arr.length; ++i) {
			int index = arr[i];

			/* if index < 0, arr[i] is already marked not missing */
			if (index < 0) {
				index += count;
			}
			/* if arr[index] >= 0, the element is new to check, mark it */
			if (arr[index] >= 0) {
				arr[index] -= count;
			}
		}

		for (int i = 0; i < arr.length; ++i) {
			if (arr[i] >= 0) {
				System.out.printf("%d is missing\n", i);
			} else {
				arr[i] += count;
			}
		}
	}

	/*
	 * { 1, 2, 1, 2, 3 }
	 *   2, 1, 1, 2, 3
	 *   1, 1, 2, 3, 3
	 *   swap to find k missing number in n
	 */
	public static List<Integer> findKMissingNumbersSwap(int[] arr) {
		assert (arr != null && arr.length >= 1);
		List<Integer> result = new LinkedList<Integer>();

		for (int i = 0; i < arr.length; ++i) {
			while (arr[i] != arr[arr[i]]) {
				HelpUtils.swap(arr, i, arr[i]);
			}
		}

		for (int i = 0; i < arr.length; ++i) {
			if (i != arr[i]) {
				result.add(i);
			}
		}

		return result;
	}

	public FindKMissingNumber() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = { 1, 2, 1, 2, 3 };
		List<Integer> result = FindKMissingNumber.findKMissingNumbersSwap(arr);
		for (int i : result) {
			System.out.printf("%d, ", i);
		}
	}

}
